#include "mainwindow.h"
#include "ui_mainwindow.h"

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <stack>
#include <QDebug>
#include <QtWidgets>
#include <QColor>

using namespace std;

template<class T>
class Stack : public stack<T> {
public:
    // 通过继承stack, 做到类似java的效果:  弹出栈顶元素，并返回该元素
    T pop() {
        T tmp = Stack::top();
        stack<T>::pop();
        return tmp;
    }
};
// 数组坐标点类
class Cell {
public:
    Cell(int i = 0, int j = 0) {
        x = i; y = j;
    }
    // 比较两个点的坐标是否相同
    bool operator== (const Cell& c) const {
        return x == c.x && y == c.y;
    }
private:
    int x, y;
    friend class Maze;
};
// 迷宫类
class Maze {
    // 全局函数做友元的声明，让外部的函数能访问Maze里面的私有属性（运算符重载函数的实现在最后那一部分）
    friend ostream& operator<< (ostream&, const Maze&);
public:
    Maze(QStringList arr);
    QVector<QStringList> exitMaze();
private:
    // 当前坐标点(cur)，出口节点（exit/e），入口节点(mouse/m)
    Cell currentCell, exitCell, entryCell;
    // 出口、入口、访问过的位置、通路、墙壁
    const char exitMarker, entryMarker, visited, passage, wall;
    // 另一个栈：记录过的坐标点
    Stack<Cell> mazeStack;
    char** store; // array of strings;
    void pushUnvisited(int,int);
    int rows, cols;  // 用户输入的行数、列数，不包括最外层的墙壁
};
// 迷宫类构造函数: 根据用户输入的矩阵来进行初始化
Maze::Maze(QStringList arr) : exitMarker('e'), entryMarker('m'), visited('.'),
            passage('0'), wall('1') {
    Stack<char*> mazeRows;
    char str[80], *s;
    int col, row = 0;
    // 用户输入矩阵，一次输入一行并回车（此时while部分只是增加左右两侧墙壁，没有增加上下两侧墙壁）
    for(int i = 0; i < arr.length(); i++){
        qstrcpy(str, arr[i].toStdString().c_str());
        row++;                     // 不知道用户要输入多少行，行数一直++（不包括上下两侧墙壁）
        cols = strlen(str);        // 根据输入的一行字符串就知道矩阵的列数
        s = new char[cols + 3];	   // 多了左右两列和结尾的空字符标志
        // columns;
        mazeRows.push(s);          // 将能存放一整行字符串的空字符数组s放入栈中(相当于栈中多了一个空房子来占位)
        qstrcpy(s + 1, str);        // 将用户输入的一行str拷贝到s的[1，strlen]的位置上
        s[0] = s[cols + 1] = wall; // 左右两侧加上墙壁
        s[cols + 2] = '\0';        // 要以空字符'\0'结尾
        // 在C语言中，字符串是以空字符结尾的字符数组。这是因为很多字符串处理函数，例如strlen等，是通过检测空字符来确定字符串的长度的

        // strchr():  在字符串中查找指定字符的第一次出现位置，并返回该位置的指针，找不到返回NULL
        if (strchr(s, exitMarker) != 0) {  // 在C++的早期版本中，0被定义为空指针的特殊值
            // 根据用户输入的字符串，在这一行找到'e'了，初始化出口节点的坐标
            exitCell.x = row;
            exitCell.y = strchr(s, exitMarker) - s; // 两个地址相减得到偏移量，作为列坐标
        }
        if (strchr(s, entryMarker) != NULL) {  // 现在直接写NULL更直观
            // 根据用户输入的字符串，在这一行找到'm'了，初始化入口节点的坐标
            entryCell.x = row;
            entryCell.y = strchr(s, entryMarker) - s;
        }
    }
    rows = row;                           // 用户输入完了，行数就等于用户输入的行数
    store = new char* [rows + 2];	      // 一维指针数组
    store[0] = new char[cols + 3];	      // 第一个指针指向新建出来的上边界数组
    for (; !mazeRows.empty(); row--) {    // 根据栈的性质，要倒序记录
        store[row] = mazeRows.pop();      // 中间指针依次指向栈中弹出的每一行元素
    }
    store[rows + 1] = new char[cols + 3]; // 最后一个指针指向新建出来的下边界数组
    store[0][cols+2] = store[rows+1][cols+2] = '\0';   // 最上面、最下面两行的末尾加上结束标志符
    for (col = 0; col <= cols+1; col++) {
        store[0][col] = wall;	          // 最上行和最下行加上墙壁
        store[rows + 1][col] = wall;
    }
}
// 要多加边界判断，不能直接比较！
void Maze::pushUnvisited(int row, int col) {
    if (row > 0 && row <= rows && col > 0 && col <= cols &&
        (store[row][col] == passage || store[row][col] == exitMarker)) {
        // 将找到的通路或出口坐标点放入栈中
        mazeStack.push(Cell(row, col));
    }
}
// 老鼠走出迷宫具体过程
QVector<QStringList> Maze::exitMaze() {
    QVector<QStringList> res;
    int row, col;
    currentCell = entryCell;  // 刚开始的cur位置就是起始mouse的位置
    // 没到出口就一直循环
    while (!(currentCell == exitCell)) {
        // 每个循环都写一个二维矩阵，放进三维的res里
        QStringList list;
        // 打印整个迷宫矩阵：按行遍历，每行都输出一列store
        for (int row = 0; row <= this->rows + 1; row++){
            list.append(this->store[row]);
            qDebug() << this->store[row];
        }
        res.append(list);
        row = currentCell.x; col = currentCell.y;  // 获取当前位置的坐标值
        // cout << *this; // print a snapshot;        // 打印当前步骤的迷宫矩阵
        if (!(currentCell == entryCell))
            store[row][col] = visited;             // 走过当前位置，进行标记
        // 上下左右的顺序依次寻找
        pushUnvisited(row - 1, col);
        pushUnvisited(row + 1, col);               // 弹栈时相反，先选择最(右左下上)的道路开始(如果有的话)
        pushUnvisited(row, col - 1);
        pushUnvisited(row, col + 1);
        if (mazeStack.empty()) {                   // 栈空，走不到出口了，失败了
            cout << *this;
            qDebug() << "Failure\n";
            QMessageBox::warning(nullptr, "错误", "failure! ", QMessageBox::Ok);
            return res;
        }
        else currentCell = mazeStack.pop();        // 弹出栈顶元素，作为老鼠下一时刻选择的位置
                                                   // 不一定是原路返回，因为栈中的坐标都是老鼠可达的，可以直接选
    }
    QStringList list;
    // 打印完成时的整个迷宫矩阵：按行遍历，每行都输出一列store
    for (int row = 0; row <= this->rows + 1; row++){
        list.append(this->store[row]);
        qDebug() << this->store[row];
    }
    res.append(list);
    qDebug() << "完成！！！ ";                       // 能退出循环说明找到出口，成功了！
    return res;
}
ostream& operator<<(ostream & out, const Maze & maze) {  // 全局函数，重载打印的运算符，在上面有做友元
    // 打印整个迷宫矩阵：按行遍历，每行都输出一列store
    for (int row = 0; row <= maze.rows + 1; row++)
        out << maze.store[row] << endl;
    out << endl;
    return out;
}


MainWindow::MainWindow(QWidget *parent)
    : QMainWindow(parent)
    , ui(new Ui::MainWindow)
{
    ui->setupUi(this);
}

MainWindow::~MainWindow()
{
    delete ui;
}


void MainWindow::on_confirm_clicked()
{
    // 拿到用户输入
    QString in = ui->input->toPlainText();
    qDebug() << in;
    QStringList arr;
    QString str = "";
    for (int i = 0; i < in.length(); i++) {
        if(in[i] != '\n'){
            str += in[i];
            qDebug() << in[i];
        } else {
            qDebug() << "hh";
            arr.append(str);
            str = "";
        }
    }
    qDebug() << arr;
    qDebug() << endl;
    // 输出展示

    QVector<QStringList> res = Maze(arr).exitMaze();       // 执行走迷宫流程的函数
    QString combinedString;

    for (const auto &list : res) {
        combinedString += list.join("\n") + "\n";  // 使用逗号分隔并添加换行符
        combinedString += "\n";
    }

    // 数字过程展现 pass
    // ui->show->setPlainText(combinedString);


    // -------------迷宫可视化graph---------------
    QString text = combinedString;
    QGraphicsView *graphicsView = ui->graph;

    // 创建场景
    QGraphicsScene *scene = new QGraphicsScene(this);
    graphicsView->setScene(scene);
    int xPos = 0;
    int yPos = 0;
    for (int i = 0; i < text.length(); ++i) {
        QChar value = text.at(i);
        qDebug() << value;
        QColor color;
        if (value == '\n'){
            xPos = 0;
            yPos += 30;
            continue;
        }else if(value == '1'){
            color = QColor(10, 10, 80);
        }else if(value == '0'){
            color = Qt::white;
        }else if(value == 'e'){
            color = Qt::green;
        }else if(value == 'm'){
            color = QColor(0, 150, 250);
        }else if(value == '.'){
            color = QColor(180, 180, 180);
        }
        QGraphicsRectItem *rectItem = new QGraphicsRectItem(xPos, yPos, 40, 40);
        rectItem->setPen(Qt::NoPen);
        rectItem->setBrush(QBrush(color));

        scene->addItem(rectItem);

        xPos += 40; // 设置矩形间距
    }
}

void MainWindow::on_help_clicked()
{
    QMessageBox msgBox;
    msgBox.setWindowTitle("tips");
    msgBox.setText("请按以下规则进行输入  <br> 0 -> road <br> 1 -> wall"
                   "<br> m -> mouse <br> e ->exit <br> 以换行符结尾 ");
    msgBox.setIcon(QMessageBox::Information);
    msgBox.exec();
}
